package com.zyk.problem;

/**
 * 最好的切法, 使左右两部分的累加和最小的一个尽量大
 *
 * @author zhangsan
 * @date 2021/5/16 14:09
 */
public class BestSplitForAll {

    // 暴力尝试O(N^2)
    public static int bestSplit1(int[] arr) {
        int N = arr.length;
        int ans = 0;
        for (int i = 0; i < N - 1; i++) {
            int left = 0, right = 0;
            for (int j = 0; j <= i; j++) {
                left += arr[j];
            }
            for (int j = i + 1; j < N; j++) {
                right += arr[j];
            }
            ans = Math.max(ans, Math.min(left, right));
        }
        return ans;
    }

    // 前缀和, O(N)
    public static int bestSplit2(int[] arr) {
        int N = arr.length;
        int[] sum = new int[N];
        sum[0] = arr[0];
        for (int i = 1; i < N; i++) {
            sum[i] = sum[i - 1] + arr[i];
        }

        int ans = 0;
        for (int i = 0; i < N - 1; i++) {
            int left = sum[i], right = sum[N - 1] - sum[i];
            ans = Math.max(ans, Math.min(left, right));
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] arr = {12, 1, 5, 123, 12, 56, 1, 321, 654, 631, 321, 321, 218, 515, 213, 13, 1, 31, 23};
        System.out.println(bestSplit1(arr));
        System.out.println(bestSplit2(arr));
    }

}
